import java.util.Arrays;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;

/**
* @description: 752. 打开转盘锁
* @author hewei
* @date 2022/8/3 15:07
* @version 1.0
*/

public class OpenLock {

    public int openLock(String[] deadends, String target) {
        String start = "0000";
        HashSet<String> set = new HashSet<>(Arrays.asList(deadends));
        if (set.contains(start)) return -1;
        if (start.equals(target)) return 0;
        Deque<String> queue = new LinkedList<>();
        HashSet<String> vis = new HashSet<>();
        int ans = 0;
        vis.add(start);
        queue.add(start);
        while (!queue.isEmpty()) {
            int size = queue.size();
            ++ans;
            for (int i = 0; i < size; i++) {
                char[] chars = queue.poll().toCharArray();
                for (int j = 0; j < chars.length; j++) {
                    char temp = chars[j];
                    char add = temp == '9' ? '0' : (char) (temp + 1);
                    char minus = temp == '0' ? '9' : (char) (temp - 1);
                    for (char c : new char[]{add, minus}) {
                        chars[j] = c;
                        String s = new String(chars);
                        chars[j] = temp;
                        if (!vis.contains(s) && !set.contains(s)) {
                            if (s.equals(target)) return ans;
                            queue.add(s);
                            vis.add(s);
                        }
                    }
                }
            }
        }
        return -1;
    }
}
